/**
 * @description 二叉搜索树
 * @author 李子一
 */

export interface ITreeNode {
	value: number
	left: ITreeNode | null
	right: ITreeNode | null
}

const arr: number[] = []

/**
 * @description 前序遍历
 * @param node
 */
export function preOrderTraverse(node: ITreeNode | null) {
	if (node === null) {
		return
	}

	arr.push(node.value)
	preOrderTraverse(node.left)
	preOrderTraverse(node.right)
}

/**
 * @description 中序遍历
 * @param node
 * @returns
 */
export function inOrderTraverse(node: ITreeNode | null) {
	if (node === null) {
		return
	}

	inOrderTraverse(node.left)
	arr.push(node.value)
	inOrderTraverse(node.right)
}

/**
 * @description 后序遍历
 * @param node
 * @returns
 */
export function postOrderTraverse(node: ITreeNode | null) {
	if (node === null) {
		return
	}

	postOrderTraverse(node.left)
	postOrderTraverse(node.right)
	arr.push(node.value)
}

/**
 * description
 * @param node
 * @param k
 */
export function getKthValue(node: ITreeNode, k: number): number | null {
	inOrderTraverse(node)
	console.log(arr)

	return arr[k - 1] || null
}

const bst: ITreeNode = {
	value: 5,
	left: {
		value: 3,
		left: {
			value: 2,
			left: null,
			right: null
		},
		right: {
			value: 4,
			left: null,
			right: null
		}
	},
	right: {
		value: 7,
		left: {
			value: 6,
			left: null,
			right: null
		},
		right: {
			value: 8,
			left: null,
			right: null
		}
	}
}

// preOrderTraverse(bst)
// inOrderTraverse(bst)
// postOrderTraverse(bst)
getKthValue(bst, 3)
